package swardToOffer.struct_1_arr;

/**
 * @Author ChanZany
 * @Date 2021/5/19 15:55
 * @Version 1.0
 * 长度为n的数组里所有数字都在0~n-1区间，
 * 找出数组中任意一个重复的数字，如
 * 长度为7的数组[2,3,1,0,2,5,3] ，对应的输出是2 or 3
 * 分析：
 * 所有数字都在0~n-1区间，与数组的下标区间符合，固采用桶排序的思想解题
 */
public class DuplicatedNum {
    private int findDup(int[] nums){
        for (int i = 0; i < nums.length; i++) {
            int res = nums[i];
            if (res!=i){ //如果下标和数值不等，就交换使得nums[res]=res
                if (nums[res]==res){ //如果nums[res]==res而当前nums[i]也等于res，则重复了
                    return res;
                }
                int tmp = nums[res];
                nums[res] = nums[i];
                nums[i] = tmp;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {2,3,1,0,2,5,3};
        System.out.println(new DuplicatedNum().findDup(nums));
    }

}
